Subdev分享|Substrate背后的密码学选择

作者：刘吉洋，一块链习《Substrate 快速入门与开发实战》第 1 期结业挑战赛第 1 名、第3期助教，极客组织 Rebase 负责人，DAO 组织 CyberRepublic 开发者。

《Substrate 快速入门与开发实战》 是一块链习联合 Laminar CTO 、Substrate、Polkadot 贡献代码的 Polkadot 社区大使陈锡亮老师共同打造的全球第一门 Substrate 开发实战指南课程，也是目前全球含金量最高、知识最实战、教学模式超系统的 Substrate开发实战特训课程。

我们希望通过这门精心打磨的课程，在这一年内为全球区块链行业培养 200 位最顶尖的 Substrate 开发者。

值得一提的是，第三期也在本月15号如期开班。如果你对这门课还不太了解的话，请扫描下图中的二维码查看详细介绍：

为了丰富同学们的课程内容 ，每周日晚 8 点，《Substrate 快速入门与开发实战》开发课的内容知识拓展——助教技术分享会，是由助教们自发轮流在线上进行分享，为开发课第3期的学员们详细解读一个区块链技术或 Substrate 相关内容。

「助教技术分享会」第 1 讲为刘吉洋助教分享的「Substrate 背后的密码学」。此次分享中，他和大家畅谈了一些“开发者需要了解的密码学知识”，通过Substrate中利用的密码学算法进行一个粗略的串讲，帮助开发者快速的利用这些密码学知识，写出更好的代码。

以下为刘吉洋助教分享的复盘内容。

这次分享的主要用户是对于密码学基础知识掌握的不是特别牢靠的同学，所以我们会在介绍Substrate中用到的密码学知识之前，先介绍一些密码学中的一些基础知识。

Substrate中的密码学算法一览

首先我们快速的预览一下Substrate中提供的几种密码学算法：

哈希函数：

• sha2
• keccak
• blake2
• xxhash

椭圆曲线密码：

• ed25519
• sr255519
• secp256k1

地址格式：

• SS58

这些密码学原语的定义在代码中都有定义，可以参考链接：

https://github.com/paritytech/substrate/tree/master/primitives/core/src

文档中也有所描述，链接：

https://docs.rs/substrate-primitives/1.0.0/substrate_primitives/

哈希函数 (Hash function)

https://github.com/paritytech/substrate/blob/master/primitives/core/src/hashing.rs 

Substrate中有以下哈希函数可以选择：

• sha2
• sha2_256
• keccak
• keccak_256
• blake2
• blake2_128
• blake2_256
• blake2_512
• xxhash (twox_hash)
• twox_64
• twox_128
• twox_256

 哈希函数介绍 

哈希函数的定义是： A function that input binary data（message） and output hash value. 输入任意二进制数据（消息），生成哈希值的函数。

哈希函数也称为散列函数或者消息摘要函数（message digest function），消息也称为原像（pre-image），哈希值也称为散列值、消息摘要（message digest）或者指纹（fingerprint）。

Hash的原意是古代法语中的“斧子”，后来被形容为“剁碎的肉末”，估计是要的是用斧子一顿乱剁然后搅在一起的感觉吧。哈希函数实际上就是将消息剁碎，再混合成固定长度的哈希值。

 特点 

• 任意长度消息计算出的哈希值都是固定长度的
• 拿SHA-256来说，无论是16字节的用户密码，5M的图像，512G的U盘中的所有文件，还是1TB的硬盘文件，计算出的哈希值永远是256比特（32字节）
• 能够快速计算出哈希值
• 消息不同哈希值也不同
• 单向性

常见的哈希算法有 MD5，SHA-1，SHA-2，SHA-3。

目前不是所有的哈希函数都是安全的：

• MD5不安全，不推荐使用。
• SHA-1 2005年强抗碰撞性被王小云团队攻破，除了用于对过去生成的哈希值进行校验，不应该用于新的用途。
• SHA-2（SHA-256，SHA-384，SHA-512）是安全的。
• SHA-3（也叫Keccak [kɛtʃak]）是安全的。

 SHA-2（SHA-256，SHA-384，SHA-512）

SHA是Secure Hash Algorithm的缩写，SHA 家族包含了SHA -0到SHA -3。

SHA-2由NIST设计，2001年发布，是SHA-1的继任者，其中包含了6种哈希函数。 

实际上6种哈希函数都是由SHA-256和SHA-512衍生出来的，将SHA-256和SHA-512的的结果进行截断就得到了其它4种。

SHA-2的实现： 

https://github.com/RustCrypto/hashes Substrate中提供了 sha2_256。

 SHA-3（Keccak）

SHA-3的全称是Secure Hash Algorithm - 3。

NIST（美国国家标准与技术研究院）通过公开竞争的方式来选拔SHA-3算法，整个选拔

经历了5年的时间(11/2/2007 – 10/2/2012)，具体过程如下：

• 2007年11月，开始公开征集
• 2008年10月，征集到64个算法，其中51个进入到第一轮
• 2009年7月，14个算法进入到第二轮
• 2010年12月，5个算法进入到第三轮

   https://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf

• 2012年10月，Keccak算法被最终确定为SHA-3标准

Keccak的实现：

https://github.com/debris/tiny-keccak

Substrate中提供了 keccak_256。

 Blake2b

Blake2b算法的网站可以参考：https://blake2.net/

介绍Blake2b算法之前，先介绍一下Blake2b的前身Blake。Blake的核心算法继承自ChaCha流加密算法（Daniel J. Bernstein发明），Blake于2010年12月被列入SHA-3的最终候选名单，最终没有被选中是因为和SHA-2算法的实现有点类似，NIST的目标是SHA-3尽量与SHA-2不同。

Blake2算法继承自Blake算法，于2012年12月21日正式对外公开。Blake2速度比 MD5，SHA-1，SHA-2，SHA-3 更快（64位x64和ARM的CPU架构上），安全性优于SHA-2，与SHA-3旗鼓相当。

下面的图表是各个哈希算法的速度测试对比，可以看出Blake2b算法的速度是最快的。

上面的哈希函数速度测试是在Skylake Intel CPU上做的测试，使用的是单核CPU。如果使用多核CPU，BLAKE2的优势会更加明显。

BLAKE2 有两个主要版本，BLAKE2b（BLAKE2）和 BLAKE2s，通常所说的BLAKE2默认指BLAKE2b。BLAKE2b 为 64 位 CPU（包括 ARM Neon）优化，可以生成1-64字节的哈希值；BLAKE2s 为 8-32 位 CPU 优化，可以生成1-32 字节的哈希值。

Blake2的实现

https://github.com/cesarb/blake2-rfc

Substrate中提供了：

•  blake2_128 

•  blake2_256 

•  blake2_512

 xxHash 

xxHash的全称是Extremely fast hash algorithm，特点是速度很快。

下表是xxHash和其它哈希算法的速度测试对比，基于2核 Duo @3GHz CPU，Windows 7的32位机器做的测试，可以看出xxHash确实非常快。

xxHash的实现：

https://libraries.io/cargo/twox-hash

https://github.com/Cyan4973/xxHash

Substrate中提供了：

• twox_64
• twox_128
• twox_256

秘钥对和签名算法

秘钥对和签名算法背后的核心是椭圆曲线密码学，椭圆曲线密码学（Elliptic Curve Cryptography, ECC）包含三个方面的内容：

• 基于椭圆曲线的公钥密码（也就是秘钥对）
• 基于椭圆曲线的数字签名（ECDSA，Elliptic Curve Digital Signature Algorithm）
• 基于椭圆曲线的秘钥交换

目前Substrate提供了三种椭圆曲线密码：

• ed25519
• sr255519
• secp256k1

 椭圆曲线基础 

椭圆曲线是指由数学方程定义的一系列点。比如：

y² = x³ + ax + b 

上面的方程叫做Weierstrass/Weierstraß方程。

通过变换不同的a，b数值得到不同的曲线形状，所以我们可以说椭圆曲线是一个家族，有一系列不同的椭圆曲线。

椭圆曲线上的一些数学运算和我们常规意义上的数学运算很不一样，比如“椭圆曲线上的加法运算“是这样定义的（参照上图）：

P + Q+ R = 0 

从几何图形上来说，其中P，Q是曲线上的两个点，R是经过P，Q的直线与椭圆曲线相交的第三个点，-R就是R经过翻转得到的点。从这个加法的定义中我们发现，曲线上两个点相加后可以得到第三个点，并且仍然在这个曲线上。

当P = Q时，经过P和Q的直线是一条与曲线相切的直线。这个时候我们就可以定义标量乘法了，P + P = 2P，如果要计算nP实际上就相当于将P相加n次：              

实际上我们说的椭圆曲线是由这些离散的nP点组成的，从1P到nP，椭圆曲线既不是椭圆，也不是曲线，只是一群离散的点，基于这些点才可以生成椭圆曲线密码学需要的点。

这里我们需要知道的是，已知曲线上的点P，求nP是比较容易的，然而已知P和nP，要是想求n的话，是非常非常困难的，这个性质被成为”椭圆曲线上的离散对数问题“。

这个时候就可以介绍椭圆曲线的公钥密码了，上面公式中的n可以作为私钥，P是椭圆曲线上选定好的一个点，而nP就是公钥。

从上图我们可以直观的看到，如果椭圆曲线的形状变了，那得到的公钥的结果也会不一样。下面我们就介绍一下不同的椭圆曲线。

 几种不同的椭圆曲线 

先看一个上面提到过的方程，叫做Weierstrass/Weierstraß方程：

y² = x³ + ax + b

这个方程是Weierstrass/Weierstraß方程的简化版，称为”short Weierstraß format”。

实际上，所有的曲线都可以由Weierstrass/Weierstraß方程来表达，不同的曲线只是基于这个方程进行了变量的变换。

Koblitz曲线 Koblitz曲线的方程为：

y² = x³ + b

基于Koblitz曲线，当b = 0时就有了secp256k1曲线：

y² = x³ + 7

secp256k1曲线是2000年由SECG（Standards for Efficient Cryptography Group，高效密码组标准）提出的。secp256k1名字的含义：

• sec：SECG标准
• p：曲线坐标在素数域
• 256：素数是256位长
• k ：是一种 Koblitz 曲线
• 1：是第一个标准中该类型的曲线

蒙哥马利曲线 1987年，Peter L. Montgomery提出了蒙哥马利曲线（Montgomery curve），曲线的方程为：

by² = x³ + ax² + x

之后，Daniel J. Bernstein提出了名为Curve25519的蒙哥马利曲线，方程是这样的：

y² = x³ + 486662x² + x

Curve25519由著名的密码学家 Daniel J. Bernstein 于 2005年公布，但实际上直到2013年才流行起来，在众多椭圆曲线家族中，由NIST公布的Curve P曲线（使用Weierstrass曲线方程）最为常用。

2013年斯诺登曝光“棱镜计划”，指出美国国家安全局（National Security Agency，NSA）在NIST标准中使用的Dual_EC_DRBG算法放置了后门，导致人们对于NIST以及其推出的Curve P（例如secp256r1 被称为 P-256）系列曲线的安全性开始产生了质疑，之后Curve25519开始获得广泛的关注。

Curve25519最开始被设计用来进行ECDH（Elliptic Curve Diffie-Hellman，基于椭圆曲线的DH密钥交换）。是目前最快的椭圆曲线密码之一，并且没有专利限制。

最开始Curve25519是被命名为DH（Diffie-Hellman密钥交换）函数的，后来为了区分DH函数和DH函数所使用的椭圆曲线，将DH函数命名为X25519，将其所用的椭圆曲线命名为Curve25519。

Edwards曲线 还有一种曲线叫做Edwards曲线（爱德华兹曲线），方程式为：

x² + y² = 1 + dx²y²

基于Edwards曲线，发明了Twisted Edwards曲线（扭曲爱德华兹曲线，也称为edwards25519 ），Twisted Edwards曲线是Edwards曲线的一般化形式，方程为：

ax² + y² = 1 + dx²y²

有意思的是，这几个曲线中是有等价关系的。通过一定的映射，蒙哥马利曲线可以转化为Weierstrass曲线。蒙哥马利曲线和Twisted Edwards曲线具有双有理等价关系，通过双有理映射也可以相互转化。

 使用椭圆曲线进行签名 

了解了哈希函数和椭圆曲线，我们来说说椭圆曲线的签名算法。

其实所有的签名都是“先哈希再签名(hash-then-sign)”，也就是先对消息进行哈希运算得到一个固定长度的哈希值，然后对这个哈希值利用签名算法进行签名。当使用椭圆曲线的签名算法的时候，利用了椭圆曲线上的离散对数问题，使得签名无法被伪造，并且可以很容易的验证签名的有效性，知道是不是给定的公钥签名的。

我们看一下签名的过程。

进行签名时，首先通过私钥a执行公私钥生成算法，得到两个值：

• 公钥A
• 随机数k

然后进行签名算法的计算：

1. 计算随机数 r = H(k, M)。其中H是哈希函数，k是上面得到的随机数，M是消息。
2. 计算随机点 R = rG。其中G是椭圆曲线上被选定的一个点，每个椭圆曲线都有这个预设值。通过前面的知识我们可以知道R也在椭圆曲线上。
3. 计算签名 s = (r + H(R, A, M) x) mod p。其中p是一个很大的质数，x是对应公钥A的私钥，mod p 表示前面得到的值对p进行模的运算。

最终得到的 (R, s) 就是数字签名。

验证签名时，使用公开的三个参数和一个公式就可以验证了。三个参数包括：

• 公钥A
• 签名 (R, s)
• 消息M

然后验证公式是否成立： sG = R + H(R, A, M) A

 Ed25519签名算法 

Ed25519的目标是在保证安全的前提下，提升性能。

和ECDSA 类似，EdDSA（Edwards-Curve Digital Signature Algorithm，爱德华兹曲线数字签名算法）也属于椭圆曲线密码；和ECDSA不同的是，EdDSA采用了不同的椭圆曲线和签名算法。

EdDSA 采用了Twisted Edwards曲线作为椭圆曲线，签名算法采用了Schnorr算法作为签名的生成和验证。

Ed25519是一种EdDSA的实现 ，由 Daniel J. Bernstein 等人设计，采用的曲线参数完全公开，并说明了参数选取的意义，保证曲线中并未内置后门。

Ed25519实现：

https://github.com/dalek-cryptography/ed25519-dalek

 sr25519签名算法 

Substrate中还使用了一个Ed25519的衍生版本，叫做sr25519，也称为Schnorrkel/Ristretto x25519，解决了使用Ed25519实现复杂协议的安全问题。

这里简单解释一下这个安全问题。

我们需要知道的是，定义一个ECC，需要6个参数：

（p, a, b, G, n, h)

其中的h叫做余因子(cofactor)，余因子的值最好为1，要不然会产生安全问题，比如其中之一的可以导致加密货币被无限增发，Monero在2017年就发现并修复了这样一个问题，好在当时没有产生损失。

secp256k1和secp256r1的余因子是1，不存在这些安全问题；而Edwards曲线的余因子都大于4，其中Ed25519使用的曲线的余因子是8，都存在这些安全问题。

这是椭圆曲线本身的问题，如果要避免这个问题，就需要在上层使用这个曲线的地方解决这个问题，Mike Hamburg的 Decaf 论文 提供了解决这个问题的方案，并且只有非常少量的性能损耗。

简单的说，就是通过数学方法，将余因子从4转换成1。然而Decaf方案只解决了余因子为4的曲线问题，并没有解决余因子为8的曲线的问题。

为了解决这个问题， Ristretto Group 将Decaf 论文中的方法进行了改进，增加了对余因子为8的曲线的支持。

Web3基金会在 Schnorrkel 这个库中也实现了这项改进，称其为Schnorrkel/Ristretto x25519，简称sr25519，并将其用于Substrate。

这个库还支持其他的协议，例如分层确定性密钥派生（Hierarchical Deterministic Key Derivation，HDKD）, 多签（multi-signatures，MuSig）, VRF (verifiable random function，可验证随机函数)。

Substrate的账户对于ed25519和sr25519这两种签名都是支持的。对于简单的签名来讲，两种协议有用相同的安全性。

ed25519可以用来支持硬件安全模块（Hardware security module，HSM）以及需要外部秘钥管理的地方。而sr25519提供了更多的区块链友好的功能，例如分层确定性密钥派生和多签，这些复杂的协议使用sr25519来实现会更加安全。

更多的对于这部分的内容，可以参考波卡中的秘钥信息，链接

https://wiki.polkadot.network/docs/en/learn-keys 。

这里还需要提到的一个实现是bip39，增加了对sr25519的支持： 

https://github.com/paritytech/substrate-bip39

 secp256k1

因为sr25519比较新，很多硬件钱包不支持，Substrate引入了硬件支持更广泛的secp256k1曲线，并已于2019年10月上线Kusama。

secp256k1是在Bitcoin和Ethereum上使用的椭圆曲线，大家应该相对熟悉，这里不对secp256k1做过多介绍。

secp256k1实现：

https://github.com/paritytech/libsecp256k1 包含的功能：

• 从私钥生成公钥
• 给消息签名
• 验证签名
• 从签名消息中恢复出公钥
• 秘密的分享（Shared secrets，不确定是啥东西）

地址格式

Substrate上使用的地址格式叫做SS58，是专门设计给基于Substrate开发的链的。

基本的格式:

base58encode ( concat ( <address-type>, <address>, <checksum> ) )

SS58是基于比特币中使用的Base58Check地址格式开发的，设计目标是可以通过账户地址识别出不同的Substrate链。使用的base58encode编码函数和比特币中使用的编码函数是一样的，不同的地方，SS58的前缀是地址类型，校验和使用的是blake2-256哈希函数。

目前支持的一些值以及含义:

• 00000000b..00110000b (0..48): Account/address identifiers on networks:
• 00000000b (0) Polkadot Live (SS58 checksum preimage)
• 00000001b (1) Polkadot Live (AccountId checksum preimage)
• 00000010b (2) Polkadot Canary (SS58 checksum preimage)
• 00000011b (3) Polkadot Canary (AccountId checksum preimage)
• 00010000b (16) Kulupu (SS58 checksum preimage)
• 00010001b (17) Kulupu (Reserved)
• 00010100b (20) Dothereum (SS58 checksum preimage)
• 00010101b (21) Dothereum (AccountId checksum preimage)
• 00101010b (42) Generic Substrate wildcard (SS58 checksum preimage)
• 00101011b (43) Generic Substrate wildcard (AccountId checksum preimage)
• 00110000b..01000000b (48..64): Bare public keys of primary cryptography
• 00110000b (48) Schnorr_Ristretto 25519 (“S_R 25519”) key
• 00110001b (49) Edwards Ed25519 key
• 00110010b (50) ECDSA SECP256k1 key
• 01000000b..11111111b (64-255) Reserved for future address format extensions.

下面是我画的一个生成SS58的流程图，应该可以比较清楚的看到SS58的生成过程。            

总结

我们通过这次分享串讲了一下Substrate中用到的密码学知识，包括哈希函数，椭圆曲线密码，地址格式这几个方面。我也是密码学的初学者，我查阅了很多资料总结Substrate中的这些密码学知识，试图通过尽量短的时间将这些知识讲清楚，如果有问题，欢迎大家和我交流。

参考资料

blake:

• https://blake2.net/
• https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2
• https://zh.wikipedia.org/wiki/BLAKE
• https://zhuanlan.zhihu.com/p/28563960

sha:

• https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F
• https://en.wikipedia.org/wiki/SHA-2
• https://zh.wikipedia.org/wiki/SHA-2
• https://csrc.nist.gov/projects/hash-functions/sha-3-project

polkadot/substrate:

• https://wiki.polkadot.network/docs/en/learn-cryptography
• https://zhuanlan.zhihu.com/p/84322255
• https://research.web3.foundation/en/latest/polkadot/keys/
• https://github.com/paritytech/substrate/wiki/External-Address-Format-(SS58)

椭圆曲线：

• https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
• http://suntus.github.io/2019/05/31/ECC%E7%AE%97%E6%B3%95/
• https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

ed25519:

• https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/
• https://en.wikipedia.org/wiki/Curve25519
• https://en.wikipedia.org/wiki/Twisted_Edwards_curve
• https://webencrypt.org/twistededwardscurve/
• http://netinfo-security.org/article/2017/1671-1122-0-9-122.html
• https://en.wikipedia.org/wiki/EdDSA#Ed25519
• https://zhuanlan.zhihu.com/p/44243140
• https://zhuanlan.zhihu.com/p/76783431
• https://tiannian.me/2018/12/28/cryptography/ed25519/
• https://www.getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
• https://tools.ietf.org/html/rfc7748
• decaf： https://eprint.iacr.org/2015/673.pdf
• Ristretto：
• https://ristretto.group/why_ristretto.html
• https://doc.dalek.rs/curve25519_dalek/ristretto/index.html

secp256k1:

• https://www.oreilly.com/library/view/mastering-bitcoin-2nd/9781491954379/ch04.html
• https://medium.com/polkadot-network/kusama-cc-2-prepos-a0ce785bb629
• https://www.johndcook.com/blog/2018/08/21/a-tale-of-two-elliptic-curves/
• https://www.johndcook.com/blog/2018/08/14/bitcoin-elliptic-curves/
• https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%AF%86%E7%A0%81%E5%AD%A6
• https://en.bitcoin.it/wiki/Secp256k1
• https://www.ietf.org/rfc/rfc5480.txt
• https://learnblockchain.cn/books/geth/part3/sign-and-valid.html
• https://crypto.stackexchange.com/questions/58506/what-is-the-curve-type-of-secp256k1

活动预告

1月4日，一块+联合Parity 、Web3、Polka Wrold 将在清华大学举办「 Subdev Beijing0.1 」Substrate 开发者的聚会。 

本次聚会邀请了 8 位 Substrate 早期贡献者和参与者，包括 Laminar CTO 陈锡亮、Plsam CEO Sota、波卡技术大使 John、Phala Network 联合创始人尹航 、Rebase 负责人刘吉洋、Prochain 联合创始人 EricZhang 一起来跟大家聊聊在 Substrate 中的开发经验以及 Substrate 的未来发展。快快扫描下方二维码来报名啦~

更多阅读：